package DataStructureAndAlgorithm.Tedukuri.位运算;
import java.util.Scanner;
// 一种基本的方法就是简单的按照a^b的方法累乘，但是这样计算的时间复杂度是O(n)的，如果b很大的话，会超时
// 一种优化方法是，按照b的二进制来累乘，计算出b的二进制表达，然后将其分解为2的幂相加的形式，然后计算出a^(2^n)，
// 这样可以将时间复杂度降低到log(N)

// 这里必须使用long类型，不然对于某些比较大的数会溢出
public class AcWing_89 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int p = in.nextInt();
        int ans = 1 % p;
        for (; b != 0; b >>= 1){
            if ((b & 1) == 1){
                ans = (int)((long)ans * a % p);
            }
            a = (int)((long)a * a % p);
        }
        System.out.print(ans);
    }
}
/*
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p,在同一行用空格隔开。
输出格式
输出一个整数，表示a^b mod p的值。
数据范围
0≤a,b≤109
1≤p≤109
输入样例：
3 2 7
输出样例：
2

 */